As personal computing devices become more powerful, containing increased storage space and processing capabilities, the average user consumes an increasingly smaller percentage of those resources in performing everyday tasks. Thus, many of today's personal computing devices are often not used to their full potential because their computing abilities greatly exceed the demands most users place upon them. An increasingly popular method of deriving use and value from the unused resources of powerful modem personal computing devices is a distributed computing system, in which the computing devices act in coordination with one another to perform tasks and maintain data.
A distributed computing system can utilize a number of interconnected computing devices to achieve the performance and storage capabilities of a larger, more-expensive computing device. Thus, while each personal computing device may only have a few gigabytes of usable storage space, a distributed computing system comprising a number of such devices, can aggregate the available storage space on each individual device and present to a user a terabyte or more of useable storage space. Similarly, a distributed computing system can present to a user a large amount of useable processing power by dividing the user's tasks into smaller segments and transmitting the segments to the individual devices for processing in parallel.
In addition to providing a useful mechanism for using excess computing capacity, distributed systems can also be composed of dedicated inexpensive computing devices in order to achieve the performance and storage capabilities of a larger, more-expensive computing device. A further advantage of distributed systems is the ability to continue to operate in the face of physical difficulties that would cripple a single, larger computing device. Such difficulties could include: sustained power outages, inclement weather, flooding, terrorist activity, and the like.
However, by allowing individual users or individual sites to retain control of the devices used in a distributed system, the reliability of each device is greatly decreased. To compensate for the increased risk that any individual computing device may become disconnected from the network, turned off, suffer a system malfunction, or otherwise become unusable to the distributing computing system, redundancy can be used to allow the distributed computing system to remain operational. Thus, the information stored on any one computing device can be redundantly stored on at least one additional similar computing device, allowing the information to remain accessible, even if one or more of the computing devices fail.
Alternatively, a distributed computing system can practice complete redundancy, in which every device within the system performs identical tasks and stores identical information. Such a system can allow the distributed system to continue to perform useful operations even if all but one of the devices should fail. Alternatively, such a system can be used to allow multiple copies of the same information to be distributed throughout a geographic region. For example, a multi-national corporation can establish a world-wide distributed computing system. Such a corporation might use a number of high performance server computing devices, rather than less powerful personal computing devices, because each individual computing device would be required to service many users within that geographic region. The individual high performance devices can each perform identical tasks and store identical data, allowing users who merely seek to access the data to obtain such access from a high performance device located in a convenient location for that user.
However, distributed computing systems can be difficult to maintain. One known difficulty is synchronizing the clocks of the various computing devices that comprise the distributed computing system. If the clocks of the various computing devices are not synchronized, fatal errors could occur. For example, each computing device may be allowed to modify given files only during a given time range. If the clocks of the computing devices are not synchronized, one computing device may start modifying a file before the prior computing device has completed modifying the same file, possibly resulting in file corruption and data inconsistency or even data loss. An additional difficulty arises from the nature of the physical time keeping devices, generally crystal oscillators, found in most computing devices; namely that physical clocks do not keep perfect time, but generally drift with respect to one another. Therefore, it is not enough to only once synchronize the clocks of the computing devices in the distributed computing system. Instead, repeated execution of a clock synchronization procedure is generally required.
One method for synchronizing the clocks of the computing devices in a distributed computing environment is to simply select a device as a reference device, and synchronize the clocks of each of the other devices to the clock of the reference device. The synchronization could be initiated by each device individually, with each device communicating with the reference device to establish the time to which it should synchronize its own clock, or it could be initiated by the reference device itself, with the reference device establishing a communication channel with every other device and exchanging messages which establish a time to which the other device should synchronize its clock. An alternative synchronization method is to propagate the reference time through the network of computing devices comprising the distributed computing environment. One method for propagating a reference time through a network of computing devices so as to synchronize their clocks to the reference time is the Network Time Protocol (NTP) commonly used on the Internet.
Most common synchronization algorithms, such as those described above, are sufficiently robust that the failure of a computing device that is part of the distributed computing environment does not materially affect the synchronization of other computing devices. Instead, such failures only result in a delay that slows down, but does not otherwise affect, the synchronization. However, a malicious process can disrupt the above referenced mechanisms. For example, a process that indicates widely varying times to different computing devices at approximately the same time introduces an error that can be very difficult to react to. Such malicious processes are known in the art as Byzantine failures, and mechanisms to synchronize clocks in the presence of Byzantine failures can be unscalable, and thus unsuitable for large-scale systems.
A number of methods for synchronizing clocks in the presence of Byzantine failures are presented in the paper entitled “Byzantine Clock Synchronization” by Leslie Lamport and P. M. Melliar-Smith, dated 1984, the disclosure of which is hereby incorporated by reference, in its entirety, into the present application. One Byzantine clock synchronization algorithm reads the value of every clock in the distributed computing environment and then synchronizes its own clock to the average of the values, with the exception that if any clock differed from clock to be synchronized by more than a given amount, that clock value was replaced with the value of the clock to be synchronized. Another Byzantine clock synchronization algorithm relies on the property that in any system having a maximum off failures, malicious or otherwise, any group of f+1 messages containing the same value must be true and a group of 2f+1 messages can be used to prove the truthfulness of the messages to a subsequent recipient. Therefore, the clock synchronization algorithm seeks to obtain either 2f+1 messages by having a computing device send the current value of its clock to every other computing device, and then having those other computing devices relay the value to every computing device, or seeks to obtain f+1 signed messages by having a computing device sign the current value of its clock when it is sent to every other computing device and then having those other computing devices sign the signed message and relay it to every computing device.
Unfortunately, even Byzantine-fault-tolerant algorithms, such as those described above, cannot perfectly synchronize the clocks of the computing devices that comprise the distributed computing system. For example, in order to synchronize their clocks, the computing devices will have to read each other's clocks. Reading a clock is a finite operation, which can involve multiple steps, including determining an appropriate location in memory, and reading the value out of that location in memory. Such delays can affect the accuracy of the synchronization. Another source of error can be the time required to transmit synchronization messages across a communications medium, such as a wired or wireless network. Consequently, even the most robust of algorithms cannot perfectly synchronize a set of clocks.
However, for all but the most time-critical applications, clock accuracy within a range can be an acceptable alternative to a perfectly synchronized series of clocks. For example, if one of the computing devices in the distributed computing environment is allowed to edit a particular file until 9:00 pm, and another computing device is allowed to edit that same file starting at 9:00 pm, it is not necessary that the devices exchange editing capabilities at exactly 9:00 pm. Rather, the only requirement for file integrity is that one device finish editing the file before the other device begins editing the file. However, while the clock synchronization algorithms described above seek to synchronize each clock to a particular reference time by minimizing the error, none of the algorithms quantify the error. Consequently, a computing device may believe its clock is synchronized to the reference time, but it does not have strong bounds on accuracy.
Returning to the above example, if the clock of the device editing the file is a few fractions of a second slow, and the clock of the device waiting to edit the file is a few fractions of a second fast, the second device will believe that it is 9:00 pm before the first device does so, resulting in two devices editing the file at the same time, and possibly corrupting the file's data. Since it is generally not important that the devices exchange editing capabilities at exactly the same time, the system would have been better served if each device had added a mere one second buffer, such that the first device ended its editing a second early, and the second device began editing a second late. The one second is not likely to impact the devices' abilities to complete their editing tasks, and yet that same second is sufficient to prevent the devices from editing the same file at the same time, and thereby corrupting it. As can be seen, in many applications it is more important for each computing device to know with certainty a bound around the reference time than it is for the computing device to have its clock set to a scalar reference time without the guarantee of 100% accuracy.